package xyf.p09.bfs_dfs;

/**
 * ClassName: J013_MovingCount
 * Description:
 * Author: xyf
 * Date: 9/9/22 9:16 AM
 * Version: 1.0
 **/
public class J013_MovingCount
{
    public int movingCount(int m, int n, int k)
    {
        boolean[][] visited = new boolean[m][n];
        return dfs(0, 0, m, n, k, visited);
    }

    public int dfs(int row, int col, int m, int n, int k, boolean[][] visited)
    {
        if (row < 0 || col < 0 || row >= m || col >= n || sum(row) + sum(col) > k || visited[row][col])
        {
            return 0;
        }
        visited[row][col] = true;
        return 1 + dfs(row - 1, col, m, n, k, visited) + dfs(row + 1, col, m, n, k, visited)
                + dfs(row, col - 1, m, n, k, visited) + dfs(row, col + 1, m, n, k, visited);
    }

    private int sum(int num)
    {
        int sum = 0;
        while (num > 0)
        {
            int i = num % 10;
            sum += i;
            num = num / 10;
        }
        return sum;
    }
}
